支持向量机（support vector machine，SVM）是在统计学习理论（statistical learning theory，SLT）基础上发展起来的一种数据挖掘方法，1992年由Boser，Guyon和Vapnik提出，在解决小样本、非线性和高维的回归和分类问题上有许多优势。 支持向量机分为支持向量分类机和支持向量回归机。顾名思义，支持向量分类机用于研究输入变量与分类型输出变量的关系及新数据预测，简称支持向量分类（support vector classification，SVC）；支持向量回归机用于研究输入变量与数值型输出变量的关系及新数据预测，简称支持向量回归（support vector regression，SVR）。
基本原理¶
支持向量分类以训练样本集为数据对象, 通过分析输入变量和分类输 出变量之间的数量关系, 对新样本的输出变量类别值进行预测。下面以二分类为例进行说明。 给定的训练集记为 $$ T=\left\{\left(a_{1}, c_{1}\right),\left(a_{2}, c_{2}\right), \cdots,\left(a_{N}, c_{N}\right)\right\}, $$ 其中, $a_{i} \in \Omega \subset R^{n}, \Omega$ 称为输入空间, 输入空间中的每一个点 $a_{i}=\left[a_{i 1}, a_{i 2}, \cdots, a_{i n}\right]^{T}$ 由 $n$ 个属性特征组成; $c_{i} \in\{-1,1\}, i=1,2, \cdots, N$; 不妨假 设 $c_{j}=1, j=1,2, \cdots, N_{1}, c_{j}=-1, j=N_{1}+1, \cdots, N$, 即 1 类有 $N_{1}$ 个训练样本点, $-1$ 类有 $N-N_{1}$ 个训练样本点。
寻找 $R^{n}$ 上的一个实值函数 $g(x)$, 以便用分类函数 $$ f(x)=\operatorname{sgn}(g(x)) $$ 推断任意一个模式 $x=\left[x_{1}, x_{2}, \cdots, x_{n}\right]^{T} \in R^{n}$ 相对应的输出 $f(x)$ 值的问题为分 类问题。
线性可分支持向量机¶
考虑训练集 $T$, 若 $\exists \omega=\left[\omega_{1}, \omega_{2}, \cdots, \omega_{n}\right]^{T} \in R^{n}, b \in R$ 和正数 $\varepsilon$, 使得对所 有使 $c_{i}=1$ 的 $a_{i}$ 有 $\omega^{T} a_{i}+b \geq \varepsilon$, 而对所有使 $c_{i}=-1$ 的 $a_{i}$ 有 $\omega^{T} a_{i}+b \leq-\varepsilon$, 则称 训练集 $T$ 线性可分, 称相应的分类问题是线性可分的。
记两类样本集分别为 $$ M^{+}=\left\{a_{i} \mid c_{i}=1,\left(a_{i}, c_{i}\right) \in T\right\}, M^{-}=\left\{a_{i} \mid c_{i}=-1,\left(a_{i}, y_{i}\right) \in T\right\} . $$ 定义 $M^{+}$的凸包 $\operatorname{conv}\left(M^{+}\right)$为 $$ \operatorname{conv}\left(M^{+}\right)=\left\{\boldsymbol{a}=\sum_{j=1}^{N_{1}} \lambda_{j} \boldsymbol{a}_{j} \mid \boldsymbol{a}_{j} \in M^{+}, \lambda_{j} \geq 0, j=1,2, \cdots, N_{1} ; \sum_{j=1}^{N_{1}} \lambda_{j}=1\right\} $$ $M^{-}$的凸包 $\operatorname{conv}\left(M^{-}\right)$为 $$ \operatorname{conv}\left(M^{-}\right)=\left\{a=\sum_{j=N_{1}+1}^{N} \lambda_{j} a_{j} \mid a_{j} \in M^{-}, \lambda_{j} \geq 0, j=N_{1}+1, \cdots, N ; \sum_{j=N_{1}+1}^{N} \lambda_{j}=1\right\} . $$
定义 空间 $R^{n}$ 中超平面都可以写为 $\omega^{T} x+b=0$ 的形式, 参数 $(\omega, b)$ 乘以任意一个非零常数后得到的是同一个超平面, 定义满足条件 $$ \left\{\begin{array}{l} c_{i}\left(\omega^{T} a_{i}+b\right) \geq 0, \quad i=1,2, \cdots, N, \\ \min _{i=1,2,-, N}\left|\omega^{T} a_{i}+b\right|=\mathbf{1} . \end{array}\right. $$ 的超平面为训练集 $T$ 的规范超平面。
定理 当训练集 $T$ 为线性可分时, 存在唯一的规范超平面 $\omega^{T} a_{i}+b=0$, 使得 $$ \left\{\begin{array}{l} \omega^{T} a_{i}+b \geq 1, \quad c_{i}=1, \\ \omega^{T} a_{i}+b \leq-1, \quad c_{i}=-1 . \end{array}\right. $$ 满足 $\omega^{T} a_{i}+b=\pm 1$ 成立的 $a_{i}$ 称为普通支持向量。
对于线性可分的情况来说, 只有普通支持向量在建立分类超平面的时 候起到了作用, 它们通常只占样本集很小的一部分, 故而也说明支持向量具 有稀疏性。对于 $c_{i}=1$ 类的样本点, 其与规范超平面的间隔为 $$ \min _{c_{i}=1} \frac{\left|\omega^{T} a_{i}+b\right|}{\|\omega\|}=\frac{1}{\|\omega\|}, $$ 对于 $c_{i}=-1$ 类的样本点，其与规范超平面的间隔为 $$ \min _{c_{i}=-1} \frac{\left|\omega^{T} a_{i}+b\right|}{\|\omega\|}=\frac{1}{\|\omega\|} $$ 则普通支持向量间的间隔为 $\frac{2}{\|\omega\|^{\circ}}$ 。
最优超平面即意味着最大化 $\frac{2}{\|\omega\|}$, 如图所示, $\omega^{T} a_{i}+b=\pm 1$ 称为分类边界, 于是寻找最优超平面的问题可以转化为如下的二次规划问题 $\min \frac{1}{2}\|\omega\|^{2}$, s.t. $c_{i}\left(\omega^{T} a_{i}+b\right) \geq 1, \quad i=1,2 \cdots, N$. 该问题的特点是目标函数 $\frac{1}{2}\|\omega\|^{2}$ 是 $\omega$ 的凸函数, 并且约束条件都是线性的。
引入 Lagrange 函数 $$ \boldsymbol{L}(\omega, b, \alpha)=\frac{1}{2}\|\omega\|^{2}+\sum_{i=1}^{N} \alpha_{i}\left(1-c_{i}\left(\omega^{T} a_{i}+b\right)\right), $$ 其中 $\alpha=\left[\alpha_{1} \cdots, \alpha_{N}\right]^{T} \in R^{N+}$ 为 Lagrange 乘子。根据对偶的定义, 通过对原问题中各变量的偏导置零可得 $$ \begin{array}{r} \frac{\partial L}{\partial \omega}=\mathbf{0} \Rightarrow \omega=\sum_{i=1}^{N} \alpha_{i} c_{i} a_{i} \\ \frac{\partial L}{\partial b}=0 \Rightarrow \sum_{i=1}^{N} \alpha_{i} c_{i}=0 \end{array} $$
带入 Lagrange 函数化为原问题的 Lagrange 对偶问题 $$ \begin{aligned} &\max _{a}-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} c_{i} c_{j} \alpha_{i} \alpha_{j} a_{i}^{T} a_{j}+\sum_{i=1}^{N} \alpha_{i}, \\ &\text { s.t. }\left\{\begin{array}{l} \sum_{i=1}^{N} c_{i} \alpha_{i}=0, \\ \alpha_{i} \geq 0, \quad i=1,2, \cdots, N . \end{array}\right. \end{aligned} $$
求解上述最优化问题, 得到最优解 $\alpha^{*}=\left[\alpha_{1}^{*}, \cdots, \alpha_{N}^{*}\right]^{T}$, 计算 $$ \omega^{*}=\sum_{i=1}^{N} \alpha_{i}^{*} c_{i} a_{i}, $$ 由 KKT 互补条件知 $$ \alpha_{i}^{*}\left(1-c_{i}\left(\omega^{* T} a_{i}+b^{*}\right)\right)=0, $$ 可得只有当 $a_{i}$ 为支持向量的时候，对应的 $\alpha_{i}^{*}$ 才为正, 否则皆为零。选择 $\alpha^{*}$ 的一个正分量 $\alpha_{j}^{*}$, 并以此计算 $$ b^{*}=c_{j}-\sum_{i=1}^{N} c_{i} \alpha_{i}^{*} a_{i}^{T} a_{j}, $$
于是构造分类超平面 $\omega^{* T} x+b^{*}=0$, 并由此求得决策函数 $$ g(x)=\sum_{i=1}^{N} \alpha_{i}^{*} c_{i}\left(a_{i}^{T} x\right)+b^{*}, $$ 得到分类函数 $$ f(x)=\operatorname{sgn}\left(\sum_{i=1}^{N} \alpha_{i}^{*} c_{i} a_{i}^{T} x+b^{*}\right), $$ 从而对未知样本进行分类。
参考文献
- 司守奎，孙玺菁 Python数学实验与建模